package main

import (
	"fmt"
)

//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
//
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
//
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
//
// 示例：
//
// 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 0 -> 8
//原因：342 + 465 = 807
//
// Related Topics 链表 数学
// 👍 5422 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNode struct {
	Val int
	Next *ListNode
}

func main()  {
	l1 :=  NumToList(9999999)
	l2 := NumToList(9999)

	l := addTwoNumbers(l1, l2)

	ll := ListToNum(l)
	fmt.Println(ll)
}

// 将链表中的数字转换为数字
func ListToNum(list *ListNode) (num int) {
	num = 0
	for {
		fmt.Println(list.Val)
		num = num * 10 + list.Val
		if list.Next == nil {
			break
		}
		list = list.Next
	}
	return num
}

// 将一个整数转换为连表
func NumToList(num int) *ListNode {
	// 初始化首位节点
	lNode := ListNode{}
	curr := &lNode
	// 计算数字
	for num / 10 != num {
		// 取模
		v := num % 10
		// 生成一个节点
		ltn := ListNode{
			Val:  v,
			Next: nil,
		}
		curr.Next = &ltn
		curr = curr.Next
		num = num / 10
	}

	return lNode.Next
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	// 对两个链表计算和
	// 循环的控制条件就是两个链表不能同时为最后的节点, 如果两个节点的都是最后的节点, 则循环结束
	rList := &ListNode{} // 返回结果的链表
	curr := rList
	carry := 0 // 保存进位
	for {
		sum := l1.Val + l2.Val + carry
		carry = sum / 10
		// 将值保存在链表中
		tNode := ListNode{
			Val:  sum % 10, //取除数
			Next: nil,
		}

		curr.Next = &tNode
		curr = curr.Next
		// 如果两个链表的值都到达了最后一个节点, 则退出
		if l1.Next == nil && l2.Next == nil {
			break
		}
		// 移动下一位
		if l1.Next != nil {
			l1 = l1.Next
		} else {
			l1.Val = 0
		}

		if l2.Next != nil {
			l2 = l2.Next
		} else {
			l2.Val = 0
		}
	}

	// 计算进位数字
	if carry > 0 {
		curr.Next = &ListNode{
			Val:  carry,
			Next: nil,
		}
	}

	return rList.Next
}
//leetcode submit region end(Prohibit modification and deletion)

